#include<iostream>
#include<vector>
using namespace std;
/*
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
解题思路：
该题限定了买卖次数为2，所以我们要分别表示第一次持有股票和不持有股票以及第二次持有股票和不持有股票的状态
所以将dp数组扩展成二维且列数为4的数组
dp[i][0]表示第一次持有股票的状态
dp[i][1]表示第一次不持有股票的状态（指的是第一次卖出股票和没有第二次购入股票的时期）
dp[i][2]表示第二次持有股票的状态
dp[i][3]表示第二次不持有股票的状态
递推公式与前面类似，dp[i][0] = max(dp[i-1][0],-prices[i])
dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])
dp[i][2] = max(dp[i-1][2],dp[i-1][1]-prices[i])
dp[i][3] = max(dp[i-1][3],dp[i-1][2]+prices[i])
*/
int dp(vector<int> prices)
{
    //创建dp数组并初始化
    vector<vector<int>> dp(prices.size(),vector<int>(4));
    //第一次持有股票
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    dp[0][2] = -prices[0];
    dp[0][3] = 0;
    for(int i=1;i<prices.size();i++)
    {
        dp[i][0] = max(dp[i-1][0],-prices[i]);
        dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]);
        dp[i][2] = max(dp[i-1][2],dp[i-1][1]-prices[i]);
        dp[i][3] = max(dp[i-1][3],dp[i-1][2]+prices[i]);
    }
    return dp[prices.size()-1][3];
}
int main()
{
    cout<<"enter a number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter prices:"<<endl;
    vector<int> prices(number);
    for(int i=0;i<number;i++)
        cin>>prices[i];
    cout<<dp(prices);
    return 0;
}